import ast

# 插值方法

# x_list = ast.literal_eval(input("请输入x列表，使用逗号隔开: "))
# y_list = ast.literal_eval(input("请输入y列表，使用逗号隔开: "))
x_list = [9, 11, 13, 15, 17]
y_list = [37289, 42747, 59885, 66581, 70644]
res_dict = {10: 40262, 12: 44765, 14: 63950, 16: 68595}


# 拉格朗日插值
def lagrange(target):
    res = 0
    for i in range(len(x_list)):
        temp = y_list[i]
        for j in range(len(y_list)):
            if i != j:
                temp = temp * (target - x_list[j])
                temp = temp / (x_list[i] - x_list[j])
        res += temp
    return res, abs(res_dict[target] - res)


def get_value(n):
    val = 0
    for i in range(n + 1):
        temp = y_list[i]
        for j in range(n + 1):
            if i != j:
                temp /= (x_list[i] - x_list[j])
        val += temp
    return val


# 牛顿插值
def newton(target):
    res = 0
    for i in range(len(x_list)):
        temp = 1
        val = get_value(i)
        for j in range(i):
            temp = temp * (target - x_list[j])
        res += val * temp
    return res, abs(res_dict[target] - res)
